import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: Zhenzhou Liu
 * @create: 2024-08-28
 * @Description:
 */
public class MatrixGraph {

    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int count = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    ++count;
                    grid[i][j] = '0';
                    Queue<int[]> queue = new LinkedList<>();
                    queue.add(new int[]{i, j});
                    while (!queue.isEmpty()) {
                        int front[] = queue.poll();
                        int x = front[0], y = front[1];
                        if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                            queue.offer(new int[]{x - 1, y});
                            grid[x - 1][y] = '0';
                        }
                        if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                            queue.offer(new int[]{x, y - 1});
                            grid[x][y - 1] = '0';
                        }
                        if (x + 1 < m && grid[x + 1][y] == '1') {
                            queue.offer(new int[]{x + 1, y});
                            grid[x + 1][y] = '0';
                        }
                        if (y + 1 < n && grid[x][y + 1] == '1') {
                            queue.offer(new int[]{x, y + 1});
                            grid[x][y + 1] = '0';
                        }
                    }
                }
            }
        }
        return count;
    }


    public int numEnclaves(int[][] grid) {
        class UnionFind {
            private int[] parent;
            private int[] rank;
            private boolean[] onEdge;
            private int m, n;

            public UnionFind(int[][] grid) {
                m = grid.length;
                n = grid[0].length;
                int count = m * n;
                parent = new int[count];
                rank = new int[count];
                onEdge = new boolean[count];
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        int index = i * n + j;
                        if (grid[i][j] == 1) {
                            parent[index] = index;
                        } else {
                            parent[index] = -1;
                        }
                        rank[index] = 0;
                        if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                            onEdge[index] = true;
                        } else {
                            onEdge[index] = false;
                        }
                    }
                }
            }

            public int find(int index) {
                if (parent[index] != index) {
                    parent[index] = find(parent[index]);
                }
                return parent[index];
            }

            public void union(int x, int y) {
                int rootX = find(x), rootY = find(y);
                if (rootY != rootX) {
                    if (rank[rootX] < rank[rootY]) {
                        parent[rootX] = rootY;
                        onEdge[rootY] |= onEdge[rootX];
                    } else if (rank[rootX] > rank[rootY]) {
                        parent[rootY] = rootX;
                        onEdge[rootX] |= onEdge[rootY];
                    } else {
                        parent[rootX] = rootY;
                        onEdge[rootY] |= onEdge[rootX];
                        rank[rootY]++;
                    }
                }
            }

            public boolean isOnEdge(int x, int y) {
                int index = x * n + y;
                return onEdge[find(index)];
            }
        }

        UnionFind unionFind = new UnionFind(grid);
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    if (i + 1 < m && grid[i + 1][j] == 1)
                        unionFind.union(index, index + n);
                    if (j + 1 < n && grid[i][j + 1] == 1)
                        unionFind.union(index, index + 1);
                }
            }
        }

        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; ++j) {
                if (grid[i][j] == 1 && !unionFind.isOnEdge(i, j)) {
                    ++enclaves;
                }
            }
        }
        return enclaves;
    }

    public static void main(String[] args) {
        int[][] grid = {{0,0,0,1,1,1,0,1,0,0},{1,1,0,0,0,1,0,1,1,1},{0,0,0,1,1,1,0,1,0,0},{0,1,1,0,0,0,1,0,1,0},{0,1,1,1,1,1,0,0,1,0},{0,0,1,0,1,1,1,1,0,1},{0,1,1,0,0,0,1,1,1,1},{0,0,1,0,0,1,0,1,0,1},{1,0,1,0,1,1,0,0,0,0},{0,0,0,0,1,1,0,0,0,1}};
        MatrixGraph graph = new MatrixGraph();
        System.out.println(graph.numEnclaves(grid));

    }

}
